public class BinarySearchTree {
    public class Node {
        public int val;
        public Node left;
        public Node right;

        public Node(int val) {
            this.val = val;
        }
    }

    public Node root;

    public boolean jc(int val) {
        Node cur = root;
        while (cur != null) {
            if (val < cur.val) {
                cur = cur.left;
            } else if (val > cur.val) {
                cur = cur.right;
            } else {
                return true;
            }
        }
        return false;
    }

    public void cha(int val) {
        Node cut = new Node(val);
        if (root == null) {
            root = cut;
        }
        Node cur = root;
        Node parter = null;
        while (cur != null) {
            if (cut.val > cur.val) {
                parter = cur;
                cur = cur.right;
            } else if (val == cur.val) {
                return;
            } else {
                parter = cur;
                cur = cur.left;
            }
        }
        if (parter.val < cut.val) {//不能使用parter.left(right)！=null去判两边都是null直接后续插入不了
            parter.right = cut;
        } else {
            parter.left = cut;
        }
    }

    public void remove(int val) {
        Node cut = new Node(val);
        Node cur = root;
        Node parter = null;
        while (cur != null) {
            if (cut.val > cur.val) {
                parter = cur;
                cur = cur.right;
            } else if (val < cur.val) {
                parter = cur;
                cur = cur.left;
            } else {
                delet(parter,cur);
            }
        }
    }
    public void delet(Node parter,Node cur){
      if(cur.left!=null){
          if(cur==root){
              root=root.left;
          }
          Node lparter=null;
          while (cur!=null){
              lparter=cur;
              cur=cur.left;
          }
          parter.left=lparter;
      }else if(cur.right!=null){
          if(cur==root){
              root=root.right;
          }
          Node rparter=null;
          while (cur!=null){
              rparter=cur;
              cur=cur.right;
          }
          parter.left=rparter;
      }else {

      }

    }
}
